package com.archeocs.figone.lib;

import java.util.Iterator;
import java.util.LinkedList;

public class Permutacja implements Iterator<int[]> {
	
	private int[] csek, psek;
	int ile=0, ilePerm = 1, licznik = 0;
	
	/**
	 * Zwiększa o 1 liczbe elementow z ktorych generowana jest permutacja
	 */
	public void zwieksz()
	{
		ile++;
		csek = new int[ile];
		psek = new int[ile];
		for (int i = 0; i<ile; i++)
		{
			csek[i] = ile-i;
		}
		ilePerm *= ile;
		licznik = 0;
	}
	
	public void zmniejsz()
	{
		ilePerm /= ile;
		ile--;
		csek = new int[ile];
		psek = new int[ile];
		for (int i = 0; i < ile; i++)
			csek[i] = ile-i;
		licznik = 0;
		
	}
	
	public String toString()
	{
		String s = "%d / %d";
		return String.format(s, licznik, ilePerm);
	}
	 
	/**
	 * W tablicy o rozmiarze k znajduje największy element m należący do zbioru elementy[k-p+1:k], p = 2,3,..,k, mniejszy od elementy[k-p].
	 * Jeśli nie ma takiego to p++ 
	 * @return {p,m}
	 */
	private int[] maxless()
	{
		int s = ile-1;
		int ec = psek[s];
		int mmi = -1, mme = 0;
		while (mmi < 0)
		{
			s--;
			if (s >= 0)
				ec = psek[s];
			else
				return null;
			for (int x = s+1; x < ile; x++)
			{
				if (psek[x] > mme && psek[x] < ec)
				{
					mme = psek[x];
					mmi = x;
				}
			}
		}
		return new int[] {s,mmi};
	}
	
	/**
	 * Znajduje najwiekszy element sposrod pozostalych do ulozenia
	 * @param tb
	 * @return
	 */
	private int[] findmax(LinkedList<Integer> tb)
	{
		int mx = 0, mxi= -1;
		for (int x =0; x < tb.size(); x++)
		{
			int it;
			if ((it = tb.get(x)) > mx)
			{
				mx = it;
				mxi = x;
			}
		}
		return new int[] {mx,mxi};
	}
	
	/**
	 * Tworzy nowa permutacje w porzadku antyleksykograficznym. Wywolywane sa kolejno funkcje maxless i findmax
	 */
	private void permutacja()
	{
		psek = csek.clone();
		csek = new int[ile];
		int pivot=0, repi=-1,tx,txi,nxt = 0;
		int[] retm = maxless();
		if (retm != null)
		{
			pivot = retm[0];
			repi = retm[1];
			//System.out.format("pivot %d, repi %d\n", pivot,repi);
			csek[pivot] = psek[repi];
			for (int cs = 0;cs<pivot;cs++)
				csek[cs] = psek[cs];
			nxt = pivot+1;
		}
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for (int ts = pivot; ts < ile; ts++)
			if (ts != repi)
				tmp.add(psek[ts]);
		while (true)
		{
			int[] fm = findmax(tmp);
			tx = fm[0];
			txi = fm[1];
			if (txi > -1)
			{
				csek[nxt] = tx;
				tmp.remove(txi);
				nxt++;
			}
			else
				break;
		}
	}
	
	/**
	 * Przepisuje tablice zawierajaca permutacje w odwrotnej kolejnosci
	 * @param tb
	 * @return
	 */
	private int[] odwroc(int[] tb)
	{
		int[] tmp = new int[tb.length];
		for (int t = 0; t < tb.length; t++)
		{
			tmp[t] = tb[tb.length-1-t]-1;
		}
		return tmp;
	}
	
	@Override
	public boolean hasNext() {
		// TODO Auto-generated method stub
		return true;
	}

	@Override
	public int[] next() {
		// TODO Auto-generated method stub
		int[] retSek = csek.clone();
		permutacja();
		licznik++;
		if (licznik > ilePerm)
			licznik = 1;
		return odwroc(retSek);
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub

	}

}
